package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         1367,
		Discription: "二叉树中是否存在一条从上到下的路径等于指定链表",
		Level:       2,
		Labels: map[string]int{
			"回溯":  1,
			"双递归": 1,
		},
	})
}

//层次递归遍历每一个节点，再通过递归检查每个节点是否存在路径
func IsSubPath(head *ds.ListNode, root *ds.TreeNode) bool {
	if root == nil {
		return false
	}

	return dfs(head, root) || IsSubPath(head, root.Left) || IsSubPath(head, root.Right)
}

func dfs(listNode *ds.ListNode, treeNode *ds.TreeNode) bool {
	if listNode == nil {
		return true
	}

	if treeNode == nil {
		return false
	}

	if treeNode.Val == listNode.Val {
		return dfs(listNode.Next, treeNode.Left) || dfs(listNode.Next, treeNode.Right)
	}

	return false
}
